from collections import OrderedDict

class LRUCache:
    def __init__(self, capacity: int):
        """
        初始化LRU缓存
        :param capacity: 缓存容量
        """
        self.capacity = capacity
        self.cache = OrderedDict()

    def get(self, key: int) -> int:
        """
        获取缓存中的值
        :param key: 键
        :return: 值，如果键不存在则返回-1
        """
        if key not in self.cache:
            return -1
        
        # 将访问的键移到字典末尾（表示最近使用）
        self.cache.move_to_end(key)
        return self.cache[key]

    def put(self, key: int, value: int) -> None:
        """
        添加或更新缓存中的值
        :param key: 键
        :param value: 值
        """
        if key in self.cache:
            # 如果键已存在，更新值并移到末尾
            self.cache.move_to_end(key)
        else:
            # 如果缓存已满，删除最久未使用的项
            if len(self.cache) >= self.capacity:
                self.cache.popitem(last=False)
        
        # 添加或更新值
        self.cache[key] = value

# 测试代码
if __name__ == "__main__":
    # 创建容量为2的LRU缓存
    lru = LRUCache(2)
    
    # 测试用例
    lru.put(1, 1)  # 缓存是 {1=1}
    lru.put(2, 2)  # 缓存是 {1=1, 2=2}
    print(lru.get(1))  # 返回 1
    lru.put(3, 3)  # 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3}
    print(lru.get(2))  # 返回 -1 (未找到)
    lru.put(4, 4)  # 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3}
    print(lru.get(1))  # 返回 -1 (未找到)
    print(lru.get(3))  # 返回 3
    print(lru.get(4))  # 返回 4

import unittest

class TestLRUCache(unittest.TestCase):
    def setUp(self):
        """在每个测试方法执行前创建新的LRU缓存实例"""
        self.cache = LRUCache(2)

    def test_basic_operations(self):
        """测试基本操作：put和get"""
        self.cache.put(1, 1)
        self.assertEqual(self.cache.get(1), 1)
        self.cache.put(2, 2)
        self.assertEqual(self.cache.get(2), 2)

    def test_cache_eviction(self):
        """测试缓存淘汰机制"""
        self.cache.put(1, 1)
        self.cache.put(2, 2)
        self.cache.put(3, 3)  # 应该淘汰1
        self.assertEqual(self.cache.get(1), -1)
        self.assertEqual(self.cache.get(2), 2)
        self.assertEqual(self.cache.get(3), 3)

    def test_update_existing_key(self):
        """测试更新已存在的键"""
        self.cache.put(1, 1)
        self.cache.put(1, 2)  # 更新键1的值
        self.assertEqual(self.cache.get(1), 2)

    def test_lru_order(self):
        """测试LRU顺序"""
        self.cache.put(1, 1)
        self.cache.put(2, 2)
        self.cache.get(1)  # 访问1，使其成为最近使用的
        self.cache.put(3, 3)  # 应该淘汰2而不是1
        self.assertEqual(self.cache.get(1), 1)
        self.assertEqual(self.cache.get(2), -1)
        self.assertEqual(self.cache.get(3), 3)

    def test_empty_cache(self):
        """测试空缓存"""
        self.assertEqual(self.cache.get(1), -1)

    def test_capacity_one(self):
        """测试容量为1的缓存"""
        cache = LRUCache(1)
        cache.put(1, 1)
        cache.put(2, 2)  # 应该淘汰1
        self.assertEqual(cache.get(1), -1)
        self.assertEqual(cache.get(2), 2)

if __name__ == "__main__":
    unittest.main() 